package java_core.HuaDongChuangKou;

import java.util.*;

/**
 * 滑动窗口算法
 */
public class HuaDongChuangKou {
    public static void main(String[] args) {
    }

    //===============================================================================================

    /*3. 无重复字符的最长子串 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
    给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。*/

    //me 超时
    private static int lengthOfLongestSubstring1_3(String s) {
        if (s.equals("")) {
            return 0;
        }
        for (int i = s.length(); i >= 1; i--) {
            for (int j = 0; j <= s.length() - i; j++) {

                if (!isRepeat(s.substring(j, i + j))) {
                    return i;
                }
            }
        }
        return 1;
    }

    //判断一个字符串是否包含重复字符
    private static boolean isRepeat(String s) {
        int[] index = new int[128];
        for (int i = 0; i < s.length(); i++) {
            index[s.charAt(i)] = index[s.charAt(i)] + 1;
            if (index[s.charAt(i)] > 1) {
                return true;
            }
        }
        return false;
    }

    //滑动窗口+bitmap方式 ok
    private static int lengthOfLongestSubstring5_3(String s) {
        if (s.equals("")) {
            return 0;
        }
        int end = 0;
        int maxSize = 0;
        int[] index = new int[128];//bitmap判断是否重复
        for (int start = 0; start < s.length(); start++) {
            //重复，移动左指针，并将之前保存的字符删除
            if (start != 0) {
                index[s.charAt(start - 1)] = 0;
            }
            //不重复，右移end
            while (end < s.length() && index[s.charAt(end)] == 0) {
                index[s.charAt(end)]++;
                end++;
            }
            maxSize = Math.max(maxSize, end - start);

        }
        return maxSize;
    }

    //===============================================================================================

    /*76. 最小覆盖子串 https://leetcode-cn.com/problems/minimum-window-substring/
    给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
    示例：
    输入: S = "ADOBECODEBANC", T = "ABC"
    输出: "BANC"
    说明：
    如果 S 中不存这样的子串，则返回空字符串 ""。
    如果 S 中存在这样的子串，我们保证它是唯一的答案。*/

    //me: 能满足需求, 但是超时
    private static String minWindow1_76(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> windows = new HashMap<>();
        Map<Character, Integer> needs = new HashMap<>();
        //初始化子串需要的字符以及对应的个数
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (needs.get(c) == null) {
                needs.put(c, 1);
            } else {
                needs.put(c, needs.get(c) + 1);
            }
        }

        int end = 0;
        String chird = null;
        for (int start = 0; start < s.length(); start++) {
            //不存在则右指针右移
            while (end < s.length() && !isContant(s.substring(start, end), t, windows, needs)) {

                end++;
            }
            String newChird = s.substring(start, end);
            if (isContant(newChird, t, windows, needs)) {

                if (chird == null) {
                    chird = newChird;
                } else {
                    chird = newChird.length() > chird.length() ? chird : newChird;
                }
            }

        }
        return chird == null ? "" : chird;
    }

    /**
     * 判断str1中是否包含所有的str2的字符
     *
     * @param str1
     * @param str2
     * @return
     */
    private static boolean isContant(String str1, String str2,
                                     Map<Character, Integer> windows, Map<Character, Integer> needs) {
        if (str1.length() < str2.length()) {
            return false;
        }
        for (int i = 0; i < str1.length(); i++) {
            char c = str1.charAt(i);
            if (windows.get(c) == null) {
                windows.put(c, 1);
            } else {
                windows.put(c, windows.get(c) + 1);
            }
        }

        for (Character character : needs.keySet()) {
            if (windows.get(character) == null) {
                return false;
            }
            if (needs.get(character) > windows.get(character)) {
                windows.clear();
                return false;
            }
        }
        windows.clear();
        return true;
    }


    private static String minWindow2_76(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        //用来统计t中每个字符出现次数
        int[] needs = new int[128];
        //用来统计滑动窗口中每个字符出现次数
        int[] window = new int[128];

        for (int i = 0; i < t.length(); i++) {
            needs[t.charAt(i)]++;
        }

        int left = 0;
        int right = 0;

        String res = "";

        //目前有多少个字符
        int count = 0;

        //用来记录最短需要多少个字符。
        int minLength = s.length() + 1;

        while (right < s.length()) {
            char ch = s.charAt(right);
            window[ch]++;
            if (needs[ch] > 0 && needs[ch] >= window[ch]) {
                count++;
            }

            //移动到不满足条件为止
            while (count == t.length()) {
                ch = s.charAt(left);
                if (needs[ch] > 0 && needs[ch] >= window[ch]) {
                    count--;
                }
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    res = s.substring(left, right + 1);

                }
                window[ch]--;
                left++;

            }
            right++;

        }
        return res;
    }


    //===============================================================================================
    /*567. 字符串的排列 https://leetcode-cn.com/problems/permutation-in-string/
    给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
    换句话说: 第一个字符串的排列之一是第二个字符串的子串。
    示例1:
    输入: s1 = "ab" s2 = "eidbaooo"
    输出: True
    解释: s2 包含 s1 的排列之一 ("ba").
    示例2:
    输入: s1= "ab" s2 = "eidboaoo"
    输出: False*/
    //ok 300ms
    private static boolean checkInclusion1_567(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        for (int i = 0; i < s2.length() - s1.length() + 1; i++) {
            String substring = s2.substring(i, s1.length() + i);
            int[] index = new int[128];
            //通过数组判断字符个数是否一致
            for (int j = 0; j < s1.length(); j++) {
                index[s1.charAt(j)]--;
                index[substring.charAt(j)]++;
            }
            boolean flag = true;
            for (int j = 0; j < index.length; j++) {
                if (index[j] != 0) {
                    flag = false;
                }

            }
            if (flag) {
                return true;
            }
        }

        return false;
    }

    //3ms
    public boolean checkInclusion2_567(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 == 0) return true;
        if (len2 < len1) return false;

        char[] ss1 = s1.toCharArray(), ss2 = s2.toCharArray();

        // 对s1中的字符计数，没出现过的字符为-1
        int[] count = new int[26];
        Arrays.fill(count, -1);
        for (char c : ss1) {
            if (count[c - 'a'] == -1)
                count[c - 'a'] = 1;
            else
                count[c - 'a']++;
        }

        // 使用滑窗进行遍历
        int start = 0, end = 0;
        while (start <= len2 - len1) {      // while 1
            while (end < start + len1) {    // while 2

                // 如果对应位置为0，则移动start寻找使其不为0的点作为新起点
                if (count[ss2[end] - 'a'] == 0) {
                    while (count[ss2[end] - 'a'] == 0)
                        count[ss2[start++] - 'a']++;
                    break;
                }

                // 如果对应位置为-1，则移动start至当前end的下一个位置，并令end=start
                if (count[ss2[end] - 'a'] == -1) {
                    while (start < end)
                        count[ss2[start++] - 'a']++;
                    start++;
                    end = start;
                    break;
                }

                // 没有以上两种情况，则对应位置计数-1
                count[ss2[end++] - 'a']--;
            }

            // 如果end==start+len1，则说明while2遍历完成，未被break，因此返回true
            if (end == start + len1)
                return true;
        }
        return false;

    }


    //===============================================================================================
    /*438. 找到字符串中所有字母异位词
     https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
    给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
    字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
    说明：
    字母异位词指字母相同，但排列不同的字符串。
    不考虑答案输出的顺序。
    示例 1:
    输入:
    s: "cbaebabacd" p: "abc"
    输出:
            [0, 6]
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
    示例 2:
    输入:
    s: "abab" p: "ab"
    输出:
            [0, 1, 2]
    解释:
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。*/

    private List<Integer> findAnagrams1_438(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (p.length() > s.length()) {
            return list;
        }
        for (int i = 0; i < s.length() - p.length() + 1; i++) {
            String substring = s.substring(i, p.length() + i);
            int[] index = new int[128];
            //通过数组判断字符个数是否一致
            for (int j = 0; j < p.length(); j++) {
                index[p.charAt(j)]--;
                index[substring.charAt(j)]++;
            }
            boolean flag = true;
            for (int j = 0; j < index.length; j++) {
                if (index[j] != 0) {
                    flag = false;
                }

            }
            if (flag) {
                list.add(i);
            }
        }

        return list;
    }

    //===============================================================================================
    //239 滑动窗口最大值 https://leetcode-cn.com/problems/sliding-window-maximum/
    private static int[] maxSlidingWindow1_239(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return null;
        }
        if (nums.length < k) {
            List<Integer> list = new ArrayList<>(1);
            int[] arr = new int[1];
            arr[0] = getMaxNum(nums, 0, nums.length - 1);
            return arr;
        }

        int arr[] = new int[nums.length - k + 1];
        List<Integer> list = new ArrayList<>(nums.length - k + 1);
        for (int i = 0; i < nums.length - k + 1; i++) {
            arr[i] = getMaxNum(nums, i, i + k - 1);
        }

        return arr;

    }

    private static int getMaxNum(int[] nums, int start, int end) {
        int max = nums[start];
        for (int i = start; i <= end; i++) {
            max = Math.max(nums[i], max);
        }
        return max;
    }

    public int[] maxSlidingWindow2_239(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];

        int[] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++)
                max = Math.max(max, nums[j]);
            output[i] = max;
        }
        return output;

    }

    //动态规划
    public int[] maxSlidingWindow3_239(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        if (k == 1) return nums;

        int[] left = new int[n];
        left[0] = nums[0];
        int[] right = new int[n];
        right[n - 1] = nums[n - 1];
        for (int i = 1; i < n; i++) {
            // from left to right
            if (i % k == 0) left[i] = nums[i];  // block_start
            else left[i] = Math.max(left[i - 1], nums[i]);

            // from right to left
            int j = n - i - 1;
            if ((j + 1) % k == 0) right[j] = nums[j];  // block_end
            else right[j] = Math.max(right[j + 1], nums[j]);
        }

        int[] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++)
            output[i] = Math.max(left[i + k - 1], right[i]);

        return output;
    }

    //===================================================================================================

    /*674. 最长连续递增序列 https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
    给定一个未经排序的整数数组，找到最长且连续的的递增序列。
    示例 1:
    输入: [1,3,5,4,7]
    输出: 3
    解释: 最长连续递增序列是 [1,3,5], 长度为3。
    尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
    示例 2:
    输入: [2,2,2,2,2]
    输出: 1
    解释: 最长连续递增序列是 [2], 长度为1。*/
    private static int findLengthOfLCIS(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        int right = 0;
        int max = 0;
        int left;
        for (int i = 0; i < nums.length; i++) {
            right = i + 1;
            left = nums[i];
            while (right < nums.length && nums[right] > left) {
                left = nums[right++];
            }
            max = Math.max(max, right - i);
            if (right >= nums.length) {
                return max;
            }
        }

        return max;
    }

    //===================================================================================================



    //===================================================================================================



    //===================================================================================================




    //===================================================================================================



}
